#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

class Solution:
    """
    @param root: The root of binary tree.
    @return: True if this Binary tree is Balanced, or false.
    """
    def isBalanced(self, root):
        # write your code here
        height = self.rec_is_balance(root)
        return height != -1

    def rec_is_balance(self, root):
        # return height is balanced, else return -1
        if not root:
            return 0

        left_height = self.rec_is_balance(root.left)
        # 左子树不平衡
        if left_height == -1:
            return -1

        right_height = self.rec_is_balance(root.right)
        # 右子树不平衡
        if right_height == -1:
            return -1

        # 左右子树高度不平衡
        if abs(left_height - right_height) > 1:
            return -1
        else:
            return max(left_height, right_height) + 1


class Solution2:
    """
    @param root: The root of binary tree.
    @return: True if this Binary tree is Balanced, or false.
    """
    def isBalanced(self, root):
        # write your code here
        det, _ = self.rec_is_balance(root)
        return det

    def rec_is_balance(self, root):
        # return is_or_no and height
        if not root:
            return True, 0

        left_is, left_height = self.rec_is_balance(root.left)
        if not left_is:
            return False, -1        # 不是平衡树, 返回高度也无意义了

        right_is, right_height = self.rec_is_balance(root.right)
        if not right_is:
            return False, -1        # 不是平衡树, 返回高度也无意义了

        cur_is = abs(left_height - right_height) <= 1
        return cur_is, max(left_height, right_height) + 1


def main():
    print("start main")

    left = TreeNode(1)
    right = TreeNode(2)
    root = TreeNode(3)
    root.left, root.right = left, None
    root.left.left = right

    s = Solution()
    ret = s.isBalanced(root)
    print(ret)

if __name__ == "__main__":
    main()
